SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Optimal substructure</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Optimal substructure</span></span>

</h1>

</header>

<p>In <a href="Computer_science" title="Computer science">computer science</a>, a problem is said to have <b>optimal substructure</b> if an optimal solution can be constructed from optimal solutions of its subproblems. This property is used to determine the usefulness of greedy algorithms for a problem.<sup id="cite_ref-cormen_1-0" class="reference"><a href="#cite_note-cormen-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p><p>Typically, a <a href="Greedy_algorithm" title="Greedy algorithm">greedy algorithm</a> is used to solve a problem with optimal substructure if it can be proven by induction that this is optimal at each step.<sup id="cite_ref-cormen_1-1" class="reference"><a href="#cite_note-cormen-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> Otherwise, provided the problem exhibits <a href="Overlapping_subproblems" title="Overlapping subproblems">overlapping subproblems</a> as well, <a href="Divide_and_conquer_algorithm" class="mw-redirect" title="Divide and conquer algorithm">divide-and-conquer</a> methods or <a href="Dynamic_programming" title="Dynamic programming">dynamic programming</a> may be used. If there are no appropriate greedy algorithms and the problem fails to exhibit overlapping subproblems, often a lengthy but straightforward search of the solution space is the best alternative.

</p><p>In the application of <a href="Dynamic_programming" title="Dynamic programming">dynamic programming</a> to <a href="Optimization_(mathematics)" class="mw-redirect" title="Optimization (mathematics)">mathematical optimization</a>, <a href="Richard_Bellman" class="mw-redirect" title="Richard Bellman">Richard Bellman</a>'s <a href="Bellman_equation#Bellman's_principle_of_optimality" title="Bellman equation">Principle of Optimality</a> is based on the idea that in order to solve a dynamic optimization problem from some starting period <i>t</i> to some ending period <i>T</i>, one implicitly has to solve subproblems starting from later dates <i>s</i>, where <i>t<s<T</i>. This is an example of optimal substructure. The Principle of Optimality is used to derive the <a href="Bellman_equation" title="Bellman equation">Bellman equation</a>, which shows how the value of the problem starting from <i>t</i> is related to the value of the problem starting from <i>s</i>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Example">Example</h2></div>

<p>Consider finding a <a href="Shortest_path_problem" title="Shortest path problem">shortest path</a> for traveling between two cities by car, as illustrated in Figure 1. Such an example is likely to exhibit optimal substructure. That is, if the shortest route from Seattle to Los Angeles passes through Portland and then Sacramento, then the shortest route from Portland to Los Angeles must pass through Sacramento too. That is, the problem of how to get from Portland to Los Angeles is nested inside the problem of how to get from Seattle to Los Angeles. (The wavy lines in the graph represent solutions to the subproblems.)

</p><p>As an example of a problem that is unlikely to exhibit optimal substructure, consider the problem of finding the cheapest airline ticket from Buenos Aires to Moscow. Even if that ticket involves stops in Miami and then London, we can't conclude that the cheapest ticket from Miami to Moscow stops in London, because the price at which an airline sells a multi-flight trip is usually not the sum of the prices at which it would sell the individual flights in the trip.

</p>

<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>

<p>A slightly more formal definition of optimal substructure can be given. Let a "problem" be a collection of "alternatives", and let each alternative have an associated cost, <i>c</i>(<i>a</i>). The task is to find a set of alternatives that minimizes <i>c</i>(<i>a</i>). Suppose that the alternatives can be <a href="Partition_of_a_set" title="Partition of a set">partitioned</a> into subsets, i.e. each alternative belongs to only one subset. Suppose each subset has its own cost function. The minima of each of these cost functions can be found, as can the minima of the global cost function, <i>restricted to the same subsets</i>. If these minima match for each subset, then it's almost obvious that a global minimum can be picked not out of the full set of alternatives, but out of only the set that consists of the minima of the smaller, local cost functions we have defined. If minimizing the local functions is a problem of "lower order", and (specifically) if, after a finite number of these reductions, the problem becomes trivial, then the problem has an optimal substructure.

</p>

<div class="mw-heading mw-heading2"><h2 id="Problems_with_optimal_substructure">Problems with optimal substructure</h2></div>

<ul><li><a href="Longest_common_subsequence_problem" class="mw-redirect" title="Longest common subsequence problem">Longest common subsequence problem</a></li>

<li><a href="Longest_increasing_subsequence" title="Longest increasing subsequence">Longest increasing subsequence</a></li>

<li><a href="Longest_palindromic_substring" title="Longest palindromic substring">Longest palindromic substring</a></li>

<li><a href="Shortest_path_problem#All-pairs_shortest_paths" title="Shortest path problem">All-Pairs Shortest Path</a></li>

<li>Any problem that can be solved by <a href="Dynamic_programming" title="Dynamic programming">dynamic programming</a>.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Problems_without_optimal_substructure">Problems <i>without</i> optimal substructure</h2></div>

<ul><li><a href="Longest_path_problem" title="Longest path problem">Longest path problem</a></li>

<li><a href="Addition-chain_exponentiation" title="Addition-chain exponentiation">Addition-chain exponentiation</a></li>

<li><i>Least-cost airline fare.</i> Using online flight search, we will frequently find that the cheapest flight from airport A to airport B involves a single connection through airport C, but the cheapest flight from airport A to airport C involves a connection through some other airport D. However, if the problem takes the maximum number of layovers as a parameter, then the problem has optimal substructure. The cheapest flight from A to B that involves at most <i>k</i> layovers is either the direct flight; or the cheapest flight from A to some airport C that involves at most <i>t</i> layovers for some integer <i>t</i> with <i>0≤t<k</i>, plus the cheapest flight from C to B that involves at most <i>k−1−t</i> layovers.</li></ul>

<ul><li><a href="Dynamic_Programming" class="mw-redirect" title="Dynamic Programming">Dynamic Programming</a></li>

<li><a href="Principle_of_optimality" class="mw-redirect" title="Principle of optimality">Principle of optimality</a></li>

<li><a href="Divide_and_conquer_algorithm" class="mw-redirect" title="Divide and conquer algorithm">Divide and conquer algorithm</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFCormenLeisersonRivestStein2009" class="citation book cs1"><a href="Thomas_H._Cormen" title="Thomas H. Cormen">Cormen, Thomas H.</a>; <a href="Charles_E._Leiserson" title="Charles E. Leiserson">Leiserson, Charles E.</a>; <a href="Ron_Rivest" title="Ron Rivest">Rivest, Ronald L.</a>; <a href="Clifford_Stein" title="Clifford Stein">Stein, Clifford</a> (2009). <i>Introduction to Algorithms</i> (3rd ed.). <a href="MIT_Press" title="MIT Press">MIT Press</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-262-03384-8</bdi>.</cite></span>

</li>

</ol></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-04-16" href="https://en.wikipedia.org/wiki/?title=Optimal_substructure&oldid=1285865919">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>